package com.leetcode.partition4;

import java.util.Arrays;
import java.util.HashMap;
import java.util.LinkedList;
import java.util.Map;

/**
 * @author `RKC`
 * @date 2021/11/19 9:07
 */
public class LC397整数替换 {

    public static int integerReplacement(int n) {
        /*
        https://leetcode-cn.com/problems/integer-replacement/solution/gong-shui-san-xie-yi-ti-san-jie-dfsbfs-t-373h/
        从二进制的角度进行分析：给定起始值 nn，求解将其变为 (000...0001) (000...0001)的最小步数。
            对于偶数（二进制最低位为 00）而言，我们只能进行一种操作，其作用是将当前值 xx 其进行一个单位的右移；
            对于奇数（二进制最低位为 11）而言，我们能够进行 +1 或 -1 操作，分析两种操作为 xx 产生的影响：
                对于 +1 操作而言：最低位必然为 11，此时如果次低位为 00 的话， +1 相当于将最低位和次低位交换；如果次低位为 11 的话，+1 操作将将「从最低位开始，
                连续一段的 11」进行消除（置零），并在连续一段的高一位添加一个 11；
                对于 -1 操作而言：最低位必然为 11，其作用是将最低位的 11 进行消除。
            因此，对于 xx 为奇数所能执行的两种操作，+1 能够消除连续一段的 11，只要次低位为 11（存在连续段），应当优先使用 +1 操作，但需要注意边界 x = 3x=3 时
            的情况（此时选择 -1 操作）。
         */
        long cur = n;
        int answer = 0;
        while (cur != 1) {
            if ((cur & 1) == 0) cur >>= 1;
            else if (cur != 3 && ((cur >> 1) & 1) == 1) cur++;
            else cur--;
            answer++;
        }
        return answer;
    }

    public static void main(String[] args) {
        System.out.println(integerReplacement(2147483647));
//        System.out.println(integerReplacement(8));
    }

    private static int bfs(int n) {
        //时间复杂度O(logn)，空间复杂度O(logn)
        Map<Long, Integer> map = new HashMap<>();
        LinkedList<Long> queue = new LinkedList<>();
        queue.addLast((long) n);
        map.put((long) n, 0);
        while (!queue.isEmpty()) {
            Long cur = queue.pollFirst();
            int steps = map.get(cur);
            if (cur == 1) return steps;
            long[] next = (cur & 1) == 0 ? new long[]{cur >> 1} : new long[]{cur + 1, cur - 1};
            for (long item : next) {
                if (item == 1) return steps + 1;
                if (map.containsKey(item)) continue;
                queue.addLast(item);
                map.put(item, steps + 1);
            }
        }
        return -1;
    }

    private static int dynamicProgramming(int n) {
        //java中的数组最大只能是2147483647，该题的最大数据2147483647会测试不通过，且dp的时间复杂度为O(n)，也会超时
        int[] dp = new int[n + 1];
        dp[1] = 0;
        for (int i = 2; i <= n; i++) {
            //i为偶数：dp[i]=1+dp[i/2]，i为奇数：dp[i]=2+min(dp[i/2],dp[i/2+1])
            if (i % 2 == 0) dp[i] = 1 + dp[i / 2];
            else dp[i] = 2 + Math.min(dp[i / 2], dp[i / 2 + 1]);
        }
        return dp[n];
    }

    private static int memoization(int n, Map<Integer, Integer> memo) {
        //时间复杂度O(logn)，空间复杂度O(logn)
        if (n == 1) return 0;
        if (memo.containsKey(n)) return memo.get(n);
        //如果是偶数，只能用n/2来替换n
        if (n % 2 == 0) {
            memo.put(n, 1 + memoization(n / 2, memo));
        } else {
            //如果是奇数，可以使用n+1或者n-1来替换
            memo.put(n, 2 + Math.min(memoization(n / 2, memo), memoization(n / 2 + 1, memo)));
        }
        return memo.get(n);
    }
}
